import java.util.Stack;

public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
//        System.out.println(s.decodeString("abc"));
        int[] a = new int[]{1,2,3,4,5};
        int[] b = new int[]{3,1,2,4,5};
        System.out.println(s.validateStackSequences(a, b));
    }

    public String decodeString(String s) {
        /**
         * 解码字符串*/
        // 1 预处理
        int n = s.length();
        Stack<Integer> countStack = new Stack<>();
        Stack<StringBuilder> strStack = new Stack<>();
        strStack.push(new StringBuilder(""));
        // 2 遍历处理
        int i = 0;
        while(i < n) {
            if(s.charAt(i) >= 'a' && s.charAt(i) <= 'z') {
                // -无需解码字符串：直接提取并尾插至字符串栈栈顶元素后
                StringBuilder temp = new StringBuilder();
                while(i < n && s.charAt(i) >= 'a' && s.charAt(i) <= 'z') {
                    temp.append(s.charAt(i++));
                }
                strStack.peek().append(temp);
            } else if(s.charAt(i) >= '0' && s.charAt(i) <= '9') {
                // -为重复数字：直接压入数字栈
                int temp = 0;
                while(i < n && s.charAt(i) >= '0' && s.charAt(i) <= '9') {
                    temp = temp * 10 + (s.charAt(i++) - '0');
                }
                countStack.push(temp);
            } else if(s.charAt(i) == '[') {
                // -为左括号：将待解码字符串压入字符串栈
                i++;
                StringBuilder temp = new StringBuilder();
                while(i < n && s.charAt(i) >= 'a' && s.charAt(i) <= 'z') {
                    temp.append(s.charAt(i++));
                }
                strStack.push(temp);
            } else {
                // -为右括号：将最近入栈元素解码，并将结果尾插至字符串栈栈顶元素后
                StringBuilder temp = decode(countStack.pop(), strStack.pop());
                strStack.peek().append(temp);
                i++;
            }
        }
        // 3 返回值
        return strStack.peek().toString();
    }

    public static StringBuilder decode(int n, StringBuilder s) {
        /**
         * 解码字符串*/
        StringBuilder retStr = new StringBuilder();
        for(int i = 0; i < n; i++) {
            retStr.append(s);
        }
        return retStr;
    }

    public boolean validateStackSequences(int[] pushed, int[] popped) {
        /**
         * 验证栈序列
         *  思路：
         *      使用一个空栈进行模拟，入栈至出栈元素为止，再出栈
         *  分类讨论：
         *      入栈至制定元素后出栈，出栈队列++
         *      1，当前栈顶元素为下一个出栈元素：继续出栈，出栈队列++
         *      2，当前栈顶元素不是下一个出栈元素 或 栈为空：入栈队列++ 直至入栈到制定元素后出栈，出栈队列++
         *  判断依据：
         *      若是出栈队列全部遍历完全则返回true，否则以任何方式打断均为false
         *  本解法正确：
         *      正确原因应当是：严格按照所需元素入栈、出栈，此为模拟的一种*/
        // 1 初始化
        int n = pushed.length;
        int pushIndex = 0;
        int popIndex = 0;
        Stack<Integer> stack = new Stack<>();

        // 2 循环执行逻辑
        // -可能先全部入栈，后续慢慢出栈
        while(pushIndex <= n && popIndex < n) {
            if(stack.isEmpty() || stack.peek() != popped[popIndex]) {
              if(pushIndex == n) {
                  // -已经全部入栈，但是栈顶元素不一致
                  return false;
              }
              while(pushIndex < n && (stack.isEmpty() || stack.peek() != popped[popIndex])) {
                  stack.push(pushed[pushIndex++]);
              }
            } else {
                stack.pop();
                popIndex++;
            }
        }

        return popIndex == n;
    }
}
